/*
 * @Author: your name
 * @Date: 2024-05-28 20:06:04
 * @LastEditTime: 2024-05-28 20:12:21
 * @LastEditors: your name
 * @Description: In User Settings Edit
 * @FilePath: \undefinedc:\Users\ljg\.leetcode\1005.k-次取反后最大化的数组和.cpp
 */
/*
 * @lc app=leetcode.cn id=1005 lang=cpp
 *
 * [1005] K 次取反后最大化的数组和
 */

// @lc code=start
class Solution {
public:
    static bool cmp(int a, int b){
        return abs(a) > abs(b);
    }
    int largestSumAfterKNegations(vector<int>& nums, int k) {
        // 按照绝对值从大到小排序
        sort(nums.begin(), nums.end(), cmp);
        for(int i = 0; i< nums.size(); i++){
            if(nums[i] < 0 && k > 0){
                nums[i] = -nums[i];
                k--;
            } 
        }
        if(k % 2 == 1){
            // 奇数个k，对数组最小的元素进行反转
            nums[nums.size()-1] *= -1;
        }
        int sum = 0;
        for(auto num:nums){
            sum += num;
        }
        return sum;
    }
};
// @lc code=end

